1624G - MinOr Tree - CodeForces Solution

#include <bits/stdc++.h>

class DSU {
    std::vector<int> par, size;
    public:
    DSU(int n) : par(n), size(n, 1) { std::iota(par.begin(), par.end(), 0); }

    int Find(int x) {
        if (x == par[x]) return x;
        return (par[x] = Find(par[x]));
    }

    bool Union(int x, int y) {
        int X = Find(x);
        int Y = Find(y);
        if (X == Y) return false;
        if (X > Y) std::swap(X, Y);
        par[X] = Y; size[Y] += size[X];
        return true;
    }

    int Size(int x) { return size[Find(x)]; }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        int n, m;
        std::cin >> n >> m;
        
        std::vector<std::vector<std::pair<int, int>>> A(n + 1);

        int hpot = 0;
        
        for (int i = 0; i < m; i++) {
            int u, v, w;
            std::cin >> u >> v >> w;
            hpot = std::max(hpot, (int)log2(w));
            A[u].push_back({v, w});
            A[v].push_back({u, w});
        }

        int ans = 0;

        auto trim_graph = [&A, &n] (int x) {
            std::vector<std::vector<std::pair<int, int>>> B(n + 1);
            DSU d(n + 1);
            for (int i = 1; i <= n; i++) {
                for (auto [v, w] : A[i]) {
                    if ((w & (1 << x)) == 0) {
                        B[i].push_back({v, w});
                        d.Union(i, v);
                    }
                }
            }

            if (d.Size(1) != n) return false;

            A = B;
            return true;
        };

        for (int i = hpot; i >= 0; i--) {
            if (!trim_graph(i)) {
                ans |= (1 << i);
            }
        }

        std::cout << ans << std::endl;
    }
}